We consider a population of interconnected individuals that, with respect toa piece of information, at each time instant can be subdivided into three(time-dependent) categories: agnostics, influenced, and evangelists. Adynamical process of information diffusion evolves among the individuals of thepopulation according to the following rules. Initially, all individuals areagnostic. Then, a set of people is chosen from the outside and convinced tostart evangelizing, i.e., to start spreading the information. When a number ofevangelists, greater than a given threshold, communicate with a node v, thenode v becomes influenced, whereas, as soon as the individual v is contacted bya sufficiently much larger number of evangelists, it is itself converted intoan evangelist and consequently it starts spreading the information. Thequestion is: How to choose a bounded cardinality initial set of evangelists soas to maximize the final number of influenced individuals? We prove that theproblem is hard to solve, even in an approximate sense. On the positive side,we present exact polynomial time algorithms for trees and complete graphs. Forgeneral graphs, we derive exact parameterized algorithms. We also investigatethe problem when the objective is to select a minimum number of evangelistscapable of influencing the whole network. Our motivations to study theseproblems come from the areas of Viral Marketing and the analysis ofquantitative models of spreading of influence in social networks.
展开▼
